package com.hsc.offer.str;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author
 * @date 2025-06-08
 * @Description 3.输入一个链表，按链表值从尾到头的顺序返回一个ArrayList
 */
public class SwordFingers3 {
    public static void main(String[] args) {
        // 创建链表: 1 -> 2 -> 3 -> 4
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        System.out.println("原始链表: 1 → 2 → 3 → 4");
        System.out.println("开始递归调用...\n");

        ArrayList<Integer> result = printListFromTailToHead(head);

        System.out.println("\n最终结果: " + result);
    }


    /**
     * 递归调用实现
     * 递归深入到链表末尾，然后逐步回溯处理每个节点。
     * 执行过程
     * 递归深入阶段：
     * 从节点1开始，发现next=2 → 递归调用
     * 进入节点2，发现next=3 → 递归调用
     * 进入节点3，发现next=4 → 递归调用
     * 进入节点4，发现next=null → 触发终止条件
     * 终止条件：
     * 节点4创建新列表 [4] 并返回
     * 这是递归的最深层，开始回溯
     * 回溯阶段：
     * 回到节点3：将当前值3添加到接收的列表[4] → 返回[4,3]
     * 回到节点2：将当前值2添加到[4,3] → 返回[4,3,2]
     * 回到节点1：将当前值1添加到[4,3,2] → 返回[4,3,2,1]
     * @param listNode
     * @return
     */
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 临界值判断
        if (listNode == null) {
            System.out.println("⚠️ 当前节点为null，返回空列表");
            return new ArrayList<>();
        }

        // 打印当前节点信息
        System.out.println("├─ 进入节点: " + listNode.val + " | 下一节点: " + (listNode.next != null ? listNode.next.val : "null"));

        // 如果当前节点next不为null
        if (listNode.next != null) {
            System.out.println("│   ├─ 递归调用: printListFromTailToHead(" + listNode.next.val + ")");
            // 递归的调用就是一个个方法不断压栈的过程 栈的特点是先进后出 形成一个倒序的过程
            // 每次调用的方法 就会进行一次压栈
            // 递归调用 integers ArrayList<Integer>的创建是从尾节点进行创建的 每个方法调用都会返回一个 ArrayList<Integer>
            // 栈底的方法执行后 会进行返回集合
            ArrayList<Integer> integers = printListFromTailToHead(listNode.next);

            System.out.println("│   └─ 回溯节点: " + listNode.val +
                    " | 接收列表: " + integers +
                    " | 添加当前值");
            // 当前的节点值添加到数组中
            integers.add(listNode.val);
            return integers;
        } else {
            //  `listNode.next == null` 时，直接返回包含当前节点值的列表。这是递归的终止条件。
            // 到达链表末尾
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.add(listNode.val);

            System.out.println("│   └─ 🏁 终止条件: 末尾节点" + listNode.val +
                    " | 返回: " + arrayList);
            return arrayList;
        }
    }


    /**
     * 更好的理解递归 我们这里不自己调用自己 我们使用四个方法来模拟递归
     * 但是实际的情况中 递归是不知道需要执行多少次的 中间循环多少次不得而知 我们必须通过临界的条件跳出递归 相当于跳出循环一样
     * 我们这里使用四个方法来模拟递归 链表也是四个元素
     *  像下面的代码他们的执行过程是一模一样的 这时候我们可以省略重复的代码 然后进行执行 所以递归就是这么个执行原理
     * @param listNode
     * @return
     */
    public static ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        // 临界值判断
        if (listNode == null) {
            System.out.println("⚠️ 当前节点为null，返回空列表");
            return new ArrayList<>();
        }

        // 打印当前节点信息
        System.out.println("├─ 进入节点: " + listNode.val + " | 下一节点: " + (listNode.next != null ? listNode.next.val : "null"));

        // 如果当前节点next不为null
        if (listNode.next != null) {
            System.out.println("│   ├─ 递归调用: printListFromTailToHead(" + listNode.next.val + ")");
            // 递归的调用就是一个个方法不断压栈的过程 栈的特点是先进后出 形成一个倒序的过程
            // 每次调用的方法 就会进行一次压栈
            // 递归调用 integers ArrayList<Integer>的创建是从尾节点进行创建的 每个方法调用都会返回一个 ArrayList<Integer>
            // 栈底的方法执行后 会进行返回集合
            ArrayList<Integer> integers = printListFromTailToHeadOne(listNode.next);

            System.out.println("│   └─ 回溯节点: " + listNode.val +
                    " | 接收列表: " + integers +
                    " | 添加当前值");
            // 当前的节点值添加到数组中
            integers.add(listNode.val);
            return integers;
        } else {
            //  `listNode.next == null` 时，直接返回包含当前节点值的列表。这是递归的终止条件。
            // 到达链表末尾
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.add(listNode.val);

            System.out.println("│   └─ 🏁 终止条件: 末尾节点" + listNode.val +
                    " | 返回: " + arrayList);
            return arrayList;
        }
    }

    public static ArrayList<Integer> printListFromTailToHeadOne(ListNode listNode) {
        // 临界值判断
        if (listNode == null) {
            System.out.println("⚠️ 当前节点为null，返回空列表");
            return new ArrayList<>();
        }

        // 打印当前节点信息
        System.out.println("├─ 进入节点: " + listNode.val + " | 下一节点: " + (listNode.next != null ? listNode.next.val : "null"));

        // 如果当前节点next不为null
        if (listNode.next != null) {
            System.out.println("│   ├─ 递归调用: printListFromTailToHead(" + listNode.next.val + ")");
            // 递归的调用就是一个个方法不断压栈的过程 栈的特点是先进后出 形成一个倒序的过程
            // 每次调用的方法 就会进行一次压栈
            // 递归调用 integers ArrayList<Integer>的创建是从尾节点进行创建的 每个方法调用都会返回一个 ArrayList<Integer>
            // 栈底的方法执行后 会进行返回集合
            ArrayList<Integer> integers = printListFromTailToHeadTwo(listNode.next);

            System.out.println("│   └─ 回溯节点: " + listNode.val +
                    " | 接收列表: " + integers +
                    " | 添加当前值");
            // 当前的节点值添加到数组中
            integers.add(listNode.val);
            return integers;
        } else {
            //  `listNode.next == null` 时，直接返回包含当前节点值的列表。这是递归的终止条件。
            // 到达链表末尾
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.add(listNode.val);

            System.out.println("│   └─ 🏁 终止条件: 末尾节点" + listNode.val +
                    " | 返回: " + arrayList);
            return arrayList;
        }
    }

    public static ArrayList<Integer> printListFromTailToHeadTwo(ListNode listNode) {
        // 临界值判断
        if (listNode == null) {
            System.out.println("⚠️ 当前节点为null，返回空列表");
            return new ArrayList<>();
        }

        // 打印当前节点信息
        System.out.println("├─ 进入节点: " + listNode.val + " | 下一节点: " + (listNode.next != null ? listNode.next.val : "null"));

        // 如果当前节点next不为null
        if (listNode.next != null) {
            System.out.println("│   ├─ 递归调用: printListFromTailToHead(" + listNode.next.val + ")");
            // 递归的调用就是一个个方法不断压栈的过程 栈的特点是先进后出 形成一个倒序的过程
            // 每次调用的方法 就会进行一次压栈
            // 递归调用 integers ArrayList<Integer>的创建是从尾节点进行创建的 每个方法调用都会返回一个 ArrayList<Integer>
            // 栈底的方法执行后 会进行返回集合
            ArrayList<Integer> integers = printListFromTailToHeadThree(listNode.next);

            System.out.println("│   └─ 回溯节点: " + listNode.val +
                    " | 接收列表: " + integers +
                    " | 添加当前值");
            // 当前的节点值添加到数组中
            integers.add(listNode.val);
            return integers;
        } else {
            //  `listNode.next == null` 时，直接返回包含当前节点值的列表。这是递归的终止条件。
            // 到达链表末尾
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.add(listNode.val);

            System.out.println("│   └─ 🏁 终止条件: 末尾节点" + listNode.val +
                    " | 返回: " + arrayList);
            return arrayList;
        }
    }

    public static ArrayList<Integer> printListFromTailToHeadThree(ListNode listNode) {
        // 临界值判断
        if (listNode == null) {
            System.out.println("⚠️ 当前节点为null，返回空列表");
            return new ArrayList<>();
        }

        // 打印当前节点信息
        System.out.println("├─ 进入节点: " + listNode.val + " | 下一节点: " + (listNode.next != null ? listNode.next.val : "null"));

        // 如果当前节点next不为null
        if (listNode.next != null) {
            System.out.println("│   ├─ 递归调用: printListFromTailToHead(" + listNode.next.val + ")");
            // 递归的调用就是一个个方法不断压栈的过程 栈的特点是先进后出 形成一个倒序的过程
            // 每次调用的方法 就会进行一次压栈
            // 递归调用 integers ArrayList<Integer>的创建是从尾节点进行创建的 每个方法调用都会返回一个 ArrayList<Integer>
            // 栈底的方法执行后 会进行返回集合
            ArrayList<Integer> integers = printListFromTailToHeadThree(listNode.next);

            System.out.println("│   └─ 回溯节点: " + listNode.val +
                    " | 接收列表: " + integers +
                    " | 添加当前值");
            // 当前的节点值添加到数组中
            integers.add(listNode.val);
            return integers;
        } else {
            //  `listNode.next == null` 时，直接返回包含当前节点值的列表。这是递归的终止条件。
            // 到达链表末尾
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.add(listNode.val);

            System.out.println("│   └─ 🏁 终止条件: 末尾节点" + listNode.val +
                    " | 返回: " + arrayList);
            return arrayList;
        }
    }


    /**
     * 使用链表的方式实现
     * @param listNode
     * @return
     */
    public static ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        // 获取一个栈
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            // 将节点的值压入栈中 默认在栈的底部
            stack.push(listNode.val);
            // 获取链表当前节点的下一个节点
            listNode = listNode.next;
        }

        // 弹栈 如果栈一直不为空
        while (!stack.isEmpty()) {
            // 从栈顶拿元素
            arrayList.add(stack.pop());
        }
        return arrayList;
    }
}


/**
 * 链表节点
 */
class ListNode {

    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}